package list.functions;

import action.unary.UnaryAction;
import java.util.Iterator;
import list.functions.exceptions.DifferentListSizeException;
import list.functions.accumulator.Accumulator;
import function.binary.BinaryFunction;
import function.unary.UnaryFunction;
import function.unary.UnaryPredicate;
import list.functions.applier.Applier;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import myAnnotations.MutateArgs;
import myAnnotations.Constant;
import predicate.PredicateFunctions;

/**
 *
 * Fully Tested: No
 * Fully Documented: Yes
 * Created: 4-Mar-2012
 * Last Updated: 4-Mar-2012
 *
 * Useful functions that are standards in the Lisp family but not so much
 * in Java. Most methods operate on List or Iterable. Usually methods operate
 * on Iterables (more general than List) unless indexing is required in which
 * case arguments must be of type List.
 *  
 * @author Shimu Wu
 */
public class ListFunctions {

    /**
     * ListFunctions class has no instance methods. Only public static
     * methods. Private constructor to prevent creating ListFunctions
     * instances.
     */
    private ListFunctions() {
    }

    // ============== These DO NOT mutate the original list ==============
    // <editor-fold defaultstate="collapsed" desc="Convenient Element Retrieval Methods, Arg: List">
    /**
     * Returns the first element in the given list. Null if the given list
     * is empty.
     * @param <T>
     * @param list
     * @return 
     */
    @Constant
    public static <T> T first(List<T> list) {
        if (list.isEmpty()) {
            return null;
        }
        return list.get(0);
    }

    /**
     * Returns the second element in the given list. Null if the given list
     * has less than two elements.
     * @param <T>
     * @param list
     * @return 
     */
    @Constant
    public static <T> T second(List<T> list) {
        if (list.size() < 2) {
            return null;
        }
        return list.get(1);
    }

    /**
     * Returns the last element in the given list. Null if the given list
     * is empty.
     * @param <T>
     * @param list
     * @return 
     */
    @Constant
    public static <T> T last(List<T> list) {
        if (list.isEmpty()) {
            return null;
        }
        return list.get(list.size() - 1);
    }
    // </editor-fold>

    // <editor-fold defaultstate="collapsed" desc="Linear Search Methods, Arg: List, Iterable">
    // <editor-fold defaultstate="collapsed" desc="Returns index of an element, Arg: List">
    /**
     * Returns the index of target in the given list. Returns -1 if the
     * target is not found. The target is considered to be in the list
     * if its equals(T) method returns true with at least one element
     * in the list.
     *  
     * @param target the element to search for
     * @param list
     * @param <T> the type of the elements contained in the given list
     * @return the index of the target in the given list, -1 if the target
     * is not found
     */
    @Constant
    public static <T> int indexOf(T target, List<T> list) {
        return indexOf(PredicateFunctions.equal(target), list);
    }

    /**
     * Returns the index of target in the given list. Returns -1 if the
     * target is not found. The target is considered to be in the list
     * if the given predicate evaluates to true with at least one element
     * in the list.
     *  
     * @param predicate
     * @param list
     * @param <T> the type of the elements contained in the given list
     * @return the index of the target in the given list, -1 if the target
     * is not found
     */
    public static <T> int indexOf(UnaryFunction<T, Boolean> predicate,
            List<T> list) {
        int i = 0;
        for (T element : list) {
            if ((element != null) && (predicate.evaluate(element))) {
                return i;
            }
            i++;
        }
        return -1;
    }
    // </editor-fold>

    // <editor-fold defaultstate="collapsed" desc="Returns whether an element exists or not, Arg: Iterable">
    /**
     * Returns true if the given target equals at least one element
     * in the iterable. The target is considered to be in the iterable
     * if its equals(T) method returns true with at least one element
     * in the iterable.
     * 
     * 
     * @param target
     * @param iterable
     * @param <T> the type of the elements contained in the given iterable
     * @throws NullPointerException if the given target is null.
     * @return 
     */
    @Constant
    public static <T> boolean elementOf(T target, Iterable<T> iterable) {
        for (T element : iterable) {
            if (target.equals(element)) {
                return true;
            }
        }
        return false;
    }
    // </editor-fold>

    // <editor-fold defaultstate="collapsed" desc="Returns an element if it is found, Arg: Iterable">
    /**
     * Returns the first element that satisfy the given unary predicate,
     * returns null if no element satisfy the unary predicate.
     * 
     * @param predicate
     * @param iterable
     * @param <T> the type of the elements contained in the given iterable
     * @return 
     */
    @Constant
    public static <T> T find(UnaryFunction<T, Boolean> predicate,
            Iterable<T> iterable) {
        for (T e : iterable) {
            if (predicate.evaluate(e)) {
                return e;
            }
        }
        return null;
    }
    // </editor-fold>
    // </editor-fold>

    // <editor-fold defaultstate="collapsed" desc="Boolean methods, checks whether an iterable satisfy given predicates, Arg: Iterable">    
    /**
     * Returns true if the given UnaryPredicate holds for all element
     * of list. Returns false if the UnaryPredicate is false for at least
     * one element of the list. Returns true if the list is empty (vacuously
     * true).
     * 
     * @param predicate
     * @param list
     * @param <T> the type of the elements contained in the given list
     * @return 
     */
    @Constant
    public static <T> boolean trueForAll(UnaryFunction<T, Boolean> predicate,
            Iterable<T> list) {
        for (T element : list) {
            if (!predicate.evaluate(element)) {
                return false;
            }
        }
        return true;
    }

    /**
     * Returns true if there exists at least one element in list such that
     * predicate is true. Returns false otherwise. Returns false if the
     * list is empty.
     * 
     * @param predicate
     * @param list
     * @param <T> the type of the elements contained in the given list
     * @return 
     */
    @Constant
    public static <T> boolean exists(UnaryFunction<T, Boolean> predicate,
            Iterable<T> list) {
        return (find(predicate, list) != null);
    }
    // </editor-fold>

    // <editor-fold defaultstate="collapsed" desc="List equality, checks if two iterables contain the same elements, Arg: Iterable"> 
    /**
     * Returns true if iterable1 and iterable2 have the same size and the same
     * elements in the same order. Two elements are equal iff their equals
     * method returns true.
     * 
     * @param <T>
     * @param iterable1
     * @param iterable2
     * @return 
     */
    @Constant
    public static <T> boolean equals(Iterable<T> iterable1,
            Iterable<T> iterable2) {

        final Iterator<T> iter1, iter2;
        iter1 = iterable1.iterator();
        iter2 = iterable2.iterator();
        while (iter1.hasNext() && iter2.hasNext()) {
            if (!iter1.next().equals(iter2.next())) {
                return false;
            }
        }
        // Return true only if we got here and neither iterables have 
        // any elements left
        return (!iter1.hasNext()) && (!iter2.hasNext());
    }
    // </editor-fold>

    // <editor-fold defaultstate="collapsed" desc="Conversion Methods, convert from one type to another related type, Arg: Iterator">
    /**
     * Returns an Iterable that uses the given iterator.
     * 
     * @param <T>
     * @param iterator
     * @return 
     */
    public static <T> Iterable<T> toIterable(final Iterator<T> iterator) {
        return new Iterable<T>() {

            public Iterator<T> iterator() {
                return iterator;
            }
        };
    }
    // </editor-fold>

    // <editor-fold defaultstate="collapsed" desc="Creates a list from a bunch of elements or another list, Arg: List">
    /**
     * Returns a copy of the given list.
     * 
     * @param <T>
     * @param list
     * @return 
     */
    @Constant
    public static <T> List<T> copy(List<T> list) {
        ArrayList<T> copy = new ArrayList<T>(list.size());
        addAll(list, copy);
        return copy;
    }

    /**
     * Create a new List containing the given elements
     * 
     * @param elements
     * @param <T> the type of the elements contained in the given list
     * @return 
     */
    @Constant
    public static <T> List<T> createList(@Constant T... elements) {
        List<T> list = new ArrayList<T>(elements.length);
        addAll(list, elements);
        return list;
    }
    // </editor-fold>

    // <editor-fold defaultstate="collapsed" desc="Prints the content of an Iterable, Arg: Iterable">
    @Constant
    public static <T> void print(Iterable<T> iterable) {
        System.out.print("[");
        forEach(new UnaryAction<T>() {            
            @Override
            public void run(T arg) {
                System.out.print(arg + ", ");
           }
        }, iterable);
        System.out.println("]");
    }
    
    @Constant
    public static <T> void println(Iterable<T> iterable) {
        System.out.println("[");
        forEach(new UnaryAction<T>() {
            @Override
            public void run(T arg) {
                System.out.println(arg);
            }
        }, iterable);
        System.out.println("]");
    }

    // </editor-fold>
    
    // <editor-fold defaultstate="collapsed" desc="Mapping Function">
    /**
     * Calls the given mapper on each element of the given Iterable in the
     * order returned by the Iterable's Iterator. The return value of the 
     * mapper is returned in a iterable.
     * 
     * @param mapper
     * @param iterable 
     * @param <T> the type of the elements contained in the given iterable
     * @param <E> the type of the elements in the returned iterable
     * @return 
     */
    @Constant
    public static <T, E> List<E> map(UnaryFunction<T, E> mapper,
            Iterable<T> iterable) {
        List<E> newList = new ArrayList<E>();
        for (T e : iterable) {
            newList.add(mapper.evaluate(e));
        }
        return newList;
    }

    /**
     * Calls the given mapper on each element of the given Iterable in the
     * order returned by the Iterable's Iterator. The return value of the
     * mapper is discarded.
     * 
     * @param <T>
     * @param <E>
     * @param mapper
     * @param list 
     */
    @Constant
    public static <T, E> void forEach(UnaryAction<T> action,
            Iterable<T> list) {
        for (T e : list) {
            action.run(e);
        }
    }

    /**
     * Starting from the front of list1 and list2 til the end of the list,
     * take one element from list1 and one element from list2, then call 
     * the given mapper's evaluate method on the two elements, and put the 
     * returned value into a new list.
     * 
     * @param <T1> the type of elements contained in list1
     * @param <T2> the type of elements contained in list2
     * @param <T3> the type of elements in the returned list
     * @param mapper a BinaryFunction with an evaluate method that
     * takes two arguments of type T1 and T2, and returns a value of 
     * type T3 
     * @param list1 
     * @param list2 
     * @throws DifferentListSizeException if list1 and list2 are not the same
     * size
     * @return 
     */
    @Constant
    public static <T1, T2, T3> List<T3> map(BinaryFunction<T1, T2, T3> mapper,
            List<T1> list1, List<T2> list2) {

        if (list1.size() != list2.size()) {
            throw new DifferentListSizeException(list1.size(), list2.size());
        }

        List<T3> newList = new ArrayList<T3>(list1.size());
        for (int i = 0; i < list1.size(); i++) {
            newList.add(mapper.evaluate(list1.get(i), list2.get(i)));
        }
        return newList;
    }
    // </editor-fold>
    
    /**
     * Returns a new List containing the elements that satisfy the given
     * predicate.
     * 
     * @param predicate
     * @param list
     * @param <T> the type of the elements contained in the given list
     * @return 
     */
    @Constant
    public static <T> List<T> filter(UnaryFunction<T, Boolean> predicate,
            Iterable<T> list) {
        List<T> newList = new ArrayList<T>();

        for (T e : list) {
            if (predicate.evaluate(e)) {
                newList.add(e);
            }
        }

        return newList;
    }

    /**
     * Calls the given accumulator on each element of the list and returns
     * the result after iterating through the entire list.
     * 
     * @param <T>
     * @param <E>
     * @param accumulator
     * @param list
     * @return 
     */
    public static <T, E> E accumulate(Accumulator<T, E> accumulator,
            @Constant Iterable<T> list) {
        for (T element : list) {
            accumulator.accumulate(element);
        }
        return accumulator.getAccumulatedValue();
    }

    /**
     * Returns the result of calling this given Applier's apply method
     * on the elements of the given list. Same as calling the given Applier's
     * apply function and passing to it all the elements of the list.
     * 
     * @param applier
     * @param list
     * @param <T> the type of the elements contained in the given list
     * @param <E> the return type of this method
     * @return the result of calling this given Applier's apply method
     * on the elements of the given list
     */
    @Constant
    @SuppressWarnings("unchecked")
    public static <T, E> E apply(Applier<T, E> applier, @Constant List<T> list) {
        return applier.apply(list.toArray());
    }

    // ============== These mutate the original list ==============
    // <editor-fold defaultstate="collapsed" desc="Duplicate Removal Methods">
    /** 
     * Remove all duplicate entries in the given list. In place removal. Uses
     * different algorithms depending on whether or not the list is sorted.
     * If it is sorted this function runs in O(n) time. 
     * Note this runs in (n^2-n)/2 or O(n^2).
     * 
     * @param list
     * @param <T> the type of the elements contained in the given list
     */
    @MutateArgs
    public static <T> void removeDuplicates(List<T> list, boolean sorted) {
        if (sorted) {
            int i = 0;
            while (i < list.size() - 1) {
                if (list.get(i) != null && list.get(i).equals(list.get(i + 1))) {
                    // arbitrary which one to remove, removing i+1 saves
                    // one shift if the list must shift all the elements left
                    // during a removal operation
                    list.remove(i + 1);
                } else {
                    i++;
                }
            }
        } else {
            // Otherwise remove duplicates assuming the list is not sorted
            removeDuplicates(list);
        }

    }

    /** 
     * Remove all duplicate entries in the given list. In place removal. 
     * Note this runs in (n^2-n)/2 or O(n^2).
     * 
     * @param list
     * @param <T> the type of the elements contained in the given list
     */
    @MutateArgs
    public static <T> void removeDuplicates(List<T> list) {
        int j = 0;
        T current;

        for (int i = 0; i < list.size(); i++) {
            current = list.get(i);

            j = i + 1;
            while (j < list.size()) {
                if (list.get(j) != null && list.get(j).equals(current)) {
                    list.remove(j);
                } else {
                    j++;
                }
            }
        }
    }
    // </editor-fold>

    // <editor-fold defaultstate="collapsed" desc="Adds a bunch of elements or a list to a given list">
    /**
     * Add all the given elements into the list.
     * 
     * @param list
     * @param elements
     * @param <T> the type of the elements contained in the given list
     */
    public static <T> void addAll(@MutateArgs List<T> list,
            @Constant T... elements) {
        list.addAll(Arrays.asList(elements));
    }

    /**
     * Copy the contents of source into destination. Destination must be
     * a subtype of List<T>
     * 
     * @param source
     * @param destination 
     * @param <T> the type of the elements contained in the given list
     * @param <E> 
     */
    public static <T, L extends List<T>> void addAll(@Constant Iterable<T> source,
            @MutateArgs L destination) {
        for (T element : source) {
            destination.add(element);
        }
    }
    // </editor-fold>

    // <editor-fold defaultstate="collapsed" desc="Mutating Mapping Functions">
    /**
     * Maps the elements of the given list and set the original list to the
     * new elements.
     * 
     * @param mapper
     * @param list 
     * @param <T> the type of the elements contained in the given list
     * @return 
     */
    public static <T> void mutateMap(@Constant UnaryFunction<T, T> mapper,
            @MutateArgs List<T> list) {
        for (int i = 0; i < list.size(); i++) {
            list.set(i, mapper.evaluate(list.get(i)));
        }
    }
    // </editor-fold>
    
    public static void swap(List list, int i, int j) {
        Object temp = list.get(i);
        list.set(i, list.get(j));
        list.set(j, temp);
    }
}
